package com.spd.sort;

import java.util.Arrays;

/**
 * 归并排序，核心思想：依次从每组1个元素，2,4,。。依次进行排序，最终结果归并到一起。
 * 需要注意的是，奇数问题，在最后一次合并排序的时候，最后一个元素要和之前排序好的数组进行合并。
 * 不需要每次归并的时候都去处理一次。 
 * @author Administrator
 *
 */
public class MergeSort {

	public static int[] array = new int[]{5, 2, 4, 7, 1, 3, 9, 6, 8};
	
	/**
	 * 
	 * @param len 拆分后的子数组的长度
	 */
	public void mergeSort(int len) {
		if(len < array.length) {
			sort(len);
			mergeSort(len * 2);
		}
	}
	
	public void sort(int len) {
		//数组分组数
		int arrayCnt = (int) Math.ceil(array.length / (len + 0.0));
		if(arrayCnt == 1) {
			return;
		}
		for(int i = 0; i < arrayCnt; i+=2) {
			//排序i,i+1两个数组 
			int arr0 = i * len;
			int arr1 = arr0 + len;
			int len1 = len;
			int len2 = len;
			//最后一个单独处理。
			if(arr1 == array.length - 1) {
				len2 = 1;
			}
			System.out.println("arr0:" + arr0 + ", arr1:" + arr1 + ",len1:" + len + ",len2:" + len2);
			sort2array(arr0, arr1, len1, len2);
		}
	}
	
	/**
	 * 排序两个数组，
	 * @param arr0 第一个数组开始下标
	 * @param arr1 第二个数组开始下标
	 * @param len1 数组1长度
	 * @param len2 数组2长度
	 */
	private void sort2array(int arr0, int arr1, int len1, int len2) {
		if(arr1 >= array.length) {
			return;
		}
		//数组个数加1的目的是设置一个哨兵，不用去处理边界问题。
		int[] L = new int[len1 + 1];
		int[] R = new int[len2 + 1];
		int iIndex = 0;
		for(int i = arr0; i < arr0 + len1; i++) {
			L[iIndex++] = array[i];
		}
		L[iIndex] = Integer.MAX_VALUE;
		int jIndex = 0;
		for(int i = arr1; i < arr1 + len2; i++) {
			R[jIndex++] = array[i];
		}
		R[jIndex] = Integer.MAX_VALUE;
		int len = 0;
		int i = 0;
		int j = 0;
		while(len < len1 + len2) {
			if(L[i] < R[j]) {
				array[arr0 + len] = L[i++];
			} else {
				array[arr0 + len] = R[j++];
			}
			len++;
		}
		
	}
	
	public static void main(String[] args) {
		MergeSort mergeSort = new MergeSort();
		mergeSort.mergeSort(1);
		System.out.println(Arrays.toString(array));
	}
}
